﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using WordsGroup.Question;

namespace WordsGroup.Answer
{
    class Bob : IGroupWords
    {
        List<List<string>> groups;
        string[] strs;
        int max;
        public int GetMaxGroupValue(string str)
        {
            groups = new List<List<string>>();
            strs = str.ToLower().Split(' ');
            max = int.MinValue;

            Rec(0);

            return max;

        }

        private void Rec(int i)
        {
            if (i == strs.Length)
            {
                int cur = 0;
                foreach (var group in groups)
                {
                    cur += Calc(group);      
                }
                if (cur > max)
                {
                    max = cur;
                }
                
            }
            else
            {
                for (int j = 0; j < groups.Count; j++)
                {
                    groups[j].Add(strs[i]);
                    Rec(i + 1);
                    groups[j].Remove(strs[i]);
                }
                List<string> curStrGroup = new List<string> { strs[i] };
                groups.Add(curStrGroup);
                Rec(i + 1);
                groups.Remove(curStrGroup);

            }
        }

        private int Calc(List<string> group)
        {
            if(group.Count == 1)
            {
                return 1;
            }

            int cur = int.MaxValue;
            string lcs = group[0];
            for (int i = 1; i < group.Count(); i++)
            {
                lcs = this.LCS(lcs, group[i]);
                cur = Math.Min(cur, lcs == null ? 0 : lcs.Length);
            }
            return cur * group.Count;
        }


        public string LCS(string str1, string str2)
        {

            if (str1 == str2)
            {
                return str1;
            }
            else if (String.IsNullOrEmpty(str1) || String.IsNullOrEmpty(str2))
            {
                return null;
            }

            var d = new int[str1.Length, str2.Length];
            var index = 0;
            var length = 0;
            for (int i = 0; i < str1.Length; i++)
            {
                for (int j = 0; j < str2.Length; j++)
                {
                    var n = i - 1 >= 0 && j - 1 >= 0 ? d[i - 1, j - 1] : 0;

                    d[i, j] = str1[i] == str2[j] ? 1 + n : 0;

                    if (d[i, j] > length)
                    {
                        length = d[i, j];
                        index = i;
                    }
                }
            }

            return str1.Substring(index - length + 1, length);
        }
    }
}
